// 动态规划
// 设 f(i, j) 为从棋盘的左上角走至单元格（i，j）的礼物最大累计价值
// f(i, j) = max(f(i - 1, j), f(i, j - 1)) + grid[i][j]

var maxValue = function (grid) {
  let m = grid.length;
  let n = grid[0].length;
  for (let j = 1; j < n; j++) {
    grid[0][j] += grid[0][j - 1];
  }
  for (let i = 1; i < m; i++) {
    grid[i][0] += grid[i - 1][0];
  }
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      grid[i][j] += Math.max(grid[i][j - 1], grid[i - 1][j]);
    }
  }
  return grid[m - 1][n - 1];
};
